{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Make K-Subarray Sums Equal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeSubKSumEqual"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使子数组元素和相等"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>arr</code> 和一个整数 <code>k</code> 。数组 <code>arr</code> 是一个循环数组。换句话说，数组中的最后一个元素的下一个元素是数组中的第一个元素，数组中第一个元素的前一个元素是数组中的最后一个元素。</p>\n",
    "\n",
    "<p>你可以执行下述运算任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选中 <code>arr</code> 中任意一个元素，并使其值加上 <code>1</code> 或减去 <code>1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>执行运算使每个长度为 <code>k</code> 的 <strong>子数组</strong> 的元素总和都相等，返回所需要的最少运算次数。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组的一个连续部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,4,1,3], k = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>在下标为 1 的元素那里执行一次运算，使其等于 3 。\n",
    "执行运算后，数组变为 [1,3,1,3] 。\n",
    "- 0 处起始的子数组为 [1, 3] ，元素总和为 4 \n",
    "- 1 处起始的子数组为 [3, 1] ，元素总和为 4 \n",
    "- 2 处起始的子数组为 [1, 3] ，元素总和为 4 \n",
    "- 3 处起始的子数组为 [3, 1] ，元素总和为 4 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,5,5,7], k = 3\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>在下标为 0 的元素那里执行三次运算，使其等于 5 。在下标为 3 的元素那里执行两次运算，使其等于 5 。\n",
    "执行运算后，数组变为 [5,5,5,5] 。\n",
    "- 0 处起始的子数组为 [5, 5, 5] ，元素总和为 15\n",
    "- 1 处起始的子数组为 [5, 5, 5] ，元素总和为 15\n",
    "- 2 处起始的子数组为 [5, 5, 5] ，元素总和为 15\n",
    "- 3 处起始的子数组为 [5, 5, 5] ，元素总和为 15\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= arr[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [make-k-subarray-sums-equal](https://leetcode.cn/problems/make-k-subarray-sums-equal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [make-k-subarray-sums-equal](https://leetcode.cn/problems/make-k-subarray-sums-equal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,4,1,3]\\n2', '[2,5,5,7]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "\n",
    "        # arr[0] == arr[0 + k] == arr[0 + 2k]\n",
    "        # arr[1] == arr[1 + k] == arr[1 + 2k]\n",
    "\n",
    "        # 1、如果 k 能整除 n, 即 0、k、2k 索引相同, 则返回 0\n",
    "        \n",
    "\n",
    "        n = len(arr)\n",
    "        if k % n == 0:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        rs = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] == None:\n",
    "                # 元素已被处理过了\n",
    "                continue\n",
    "            tmp = []\n",
    "            index = i\n",
    "            while True:\n",
    "                # 添加 arr[i] arr[i+k] arr[i+2k] ... \n",
    "                tmp.append(arr[index])\n",
    "                arr[index] = None\n",
    "                index = (index + k) % n\n",
    "                if index == i:\n",
    "                    # 又回到 i\n",
    "                    break\n",
    "            # 让 arr[i] arr[i+k] arr[i+2k] 相等, 即等于中数\n",
    "            tmp.sort()\n",
    "            middle = tmp[len(tmp) // 2]\n",
    "            for num in tmp:\n",
    "                rs += abs(num - middle)\n",
    "        return rs\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def sum_arr(self, arr, k):\n",
    "        sub_sum = [0] * len(arr)\n",
    "        sub_sum[0] = sum(arr[0:k])\n",
    "        min_sub = sub_sum[0]\n",
    "        max_sub = sub_sum[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            sub_sum[i] = sub_sum[i-1] - arr[i-1] + arr[(i-1+k)%len(arr)]\n",
    "            min_sub = min(min_sub, sub_sum[i])\n",
    "            max_sub = max(max_sub, sub_sum[i])\n",
    "        return max_sub-min_sub\n",
    "\n",
    "    def find_sl(self, e_group, sl):\n",
    "        #堆排序\n",
    "        pass\n",
    "\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        # a[i] = a[i+k] = a[i+2k]... = a[(i+xk)%len(arr)]\n",
    "        # i=0,1,...k-1\n",
    "        # 一共?组，?<=len(arr) 每一组内部相同即可\n",
    "        # 每组中位数，是变动最少的\n",
    "        # 不一定一共多少组 \n",
    "        all_group = []\n",
    "        have_count = [0]*len(arr)\n",
    "\n",
    "        while 0 in have_count:\n",
    "            start = -1\n",
    "            for ei in range(len(arr)):\n",
    "                if have_count[ei] == 0:\n",
    "                    start = ei\n",
    "\n",
    "            if start!=-1:\n",
    "                current = start\n",
    "                this_count = []\n",
    "                # print(start, current)\n",
    "                while have_count[current]==0:\n",
    "                    have_count[current] = 1\n",
    "                    this_count.append(arr[current])\n",
    "                    current = (current + k)%len(arr)\n",
    "                all_group.append(this_count)\n",
    "\n",
    "        print(all_group)\n",
    "        \n",
    "        result = 0\n",
    "        for e_group in all_group:\n",
    "            # 找中位数 rank 大小第len(e_group)//2个\n",
    "            sl = len(e_group)//2\n",
    "            # 找第sl大的数\n",
    "            if len(e_group) <= 2: #只有1个或2个值\n",
    "                val = e_group[0]\n",
    "            else:\n",
    "                # val = self.find_sl(e_group, sl)\n",
    "                val = sorted(e_group)[sl]\n",
    "            for ele in e_group:\n",
    "                result += abs(ele-val)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        visit = [0]*n\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if visit[i]:\n",
    "                continue\n",
    "            x = i\n",
    "            lst = []\n",
    "            while not visit[x]:\n",
    "                visit[x] = 1\n",
    "                lst.append(arr[x])\n",
    "                x = (x+k) % n\n",
    "            lst.sort()\n",
    "            m = len(lst)\n",
    "            pre = list(accumulate(lst, initial=0))\n",
    "            cur = inf\n",
    "            for j in range(m):\n",
    "                w = j*lst[j] - pre[j] + pre[-1] - pre[j] - (m-j)*lst[j]\n",
    "                if w < cur:\n",
    "                    cur = w\n",
    "            ans += cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def sum_arr(self, arr, k):\n",
    "        sub_sum = [0] * len(arr)\n",
    "        sub_sum[0] = sum(arr[0:k])\n",
    "        min_sub = sub_sum[0]\n",
    "        max_sub = sub_sum[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            sub_sum[i] = sub_sum[i-1] - arr[i-1] + arr[(i-1+k)%len(arr)]\n",
    "            min_sub = min(min_sub, sub_sum[i])\n",
    "            max_sub = max(max_sub, sub_sum[i])\n",
    "        return max_sub-min_sub\n",
    "\n",
    "    def find_sl(self, e_group, sl):\n",
    "        #堆排序\n",
    "        pass\n",
    "\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        # a[i] = a[i+k] = a[i+2k]... = a[(i+xk)%len(arr)]\n",
    "        # i=0,1,...k-1\n",
    "        # 一共?组，?<=len(arr) 每一组内部相同即可\n",
    "        # 每组中位数，是变动最少的\n",
    "        # 不一定一共多少组 \n",
    "        all_group = []\n",
    "        have_count = [0]*len(arr)\n",
    "\n",
    "        while 0 in have_count:\n",
    "            # start = -1\n",
    "            start = have_count.index(0)\n",
    "            # for ei in range(len(arr)):\n",
    "            #     if have_count[ei] == 0:\n",
    "            #         start = ei\n",
    "\n",
    "            if start!=-1:\n",
    "                current = start\n",
    "                this_count = []\n",
    "                # print(start, current)\n",
    "                while have_count[current]==0:\n",
    "                    have_count[current] = 1\n",
    "                    this_count.append(arr[current])\n",
    "                    current = (current + k)%len(arr)\n",
    "                all_group.append(this_count)\n",
    "\n",
    "        # print(all_group)\n",
    "        \n",
    "        result = 0\n",
    "        for e_group in all_group:\n",
    "            # 找中位数 rank 大小第len(e_group)//2个\n",
    "            sl = len(e_group)//2\n",
    "            # 找第sl大的数\n",
    "            if len(e_group) <= 2: #只有1个或2个值\n",
    "                val = e_group[0]\n",
    "            else:\n",
    "                # val = self.find_sl(e_group, sl)\n",
    "                e_group.sort()\n",
    "                val = e_group[sl]\n",
    "            for ele in e_group:\n",
    "                result += abs(ele-val)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        def getans(l):\n",
    "            ret=0\n",
    "            l.sort()\n",
    "            n=len(l)\n",
    "            mid=l[n//2]\n",
    "            for i in l:\n",
    "                ret+=abs(i-mid) \n",
    "            return ret\n",
    "        n=len(arr)\n",
    "        m=gcd(n,k)\n",
    "        ls=[[0 for _ in range(n//m)] for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            a=i%m\n",
    "            b=i//m\n",
    "            ls[a][b]=arr[i]\n",
    "        #print(ls)\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            ans+=getans(ls[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def sum_arr(self, arr, k):\n",
    "        sub_sum = [0] * len(arr)\n",
    "        sub_sum[0] = sum(arr[0:k])\n",
    "        min_sub = sub_sum[0]\n",
    "        max_sub = sub_sum[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            sub_sum[i] = sub_sum[i-1] - arr[i-1] + arr[(i-1+k)%len(arr)]\n",
    "            min_sub = min(min_sub, sub_sum[i])\n",
    "            max_sub = max(max_sub, sub_sum[i])\n",
    "        return max_sub-min_sub\n",
    "\n",
    "    def find_sl(self, e_group, sl):\n",
    "        #堆排序\n",
    "        pass\n",
    "\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        # a[i] = a[i+k] = a[i+2k]... = a[(i+xk)%len(arr)]\n",
    "        # i=0,1,...k-1\n",
    "        # 一共?组，?<=len(arr) 每一组内部相同即可\n",
    "        # 每组中位数，是变动最少的\n",
    "        # 不一定一共多少组 \n",
    "        all_group = []\n",
    "        have_count = [0]*len(arr)\n",
    "\n",
    "        while 0 in have_count:\n",
    "            start = -1\n",
    "            for ei in range(len(arr)):\n",
    "                if have_count[ei] == 0:\n",
    "                    start = ei\n",
    "\n",
    "            if start!=-1:\n",
    "                current = start\n",
    "                this_count = []\n",
    "                # print(start, current)\n",
    "                while have_count[current]==0:\n",
    "                    have_count[current] = 1\n",
    "                    this_count.append(arr[current])\n",
    "                    current = (current + k)%len(arr)\n",
    "                all_group.append(this_count)\n",
    "\n",
    "        print(all_group)\n",
    "        \n",
    "        result = 0\n",
    "        for e_group in all_group:\n",
    "            # 找中位数 rank 大小第len(e_group)//2个\n",
    "            sl = len(e_group)//2\n",
    "            # 找第sl大的数\n",
    "            if len(e_group) <= 2: #只有1个或2个值\n",
    "                val = e_group[0]\n",
    "            else:\n",
    "                # val = self.find_sl(e_group, sl)\n",
    "                val = sorted(e_group)[sl]\n",
    "            for ele in e_group:\n",
    "                result += abs(ele-val)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "    \n",
    "        ret = 0\n",
    "        for i in range(k):\n",
    "            tmp = sorted(arr[j] for j in range(i, len(arr), k))\n",
    "            med = tmp[len(tmp) >> 1]\n",
    "            ret += sum(abs(v - med) for v in tmp)\n",
    "        \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int: \n",
    "\n",
    "     k=gcd(k,len(arr))\n",
    "     ans=0\n",
    "     for i in range(k):\n",
    "         b=sorted(arr[i::k])\n",
    "         mi=b[len(b)//2]\n",
    "         for x in b:\n",
    "           ans+=abs(mi-x)\n",
    "     return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr) \n",
    "        step = math.gcd(n, k)\n",
    "        ans = 0\n",
    "        for i in range(step):\n",
    "            brr = sorted([arr[j] for j in range(i, n, step)])\n",
    "            m = len(brr)\n",
    "            #print(brr)\n",
    "            for x in brr:\n",
    "                ans += abs(x - brr[m//2])\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        gcd = math.gcd(len(arr), k)\n",
    "        ans = 0\n",
    "        for i in range(gcd):\n",
    "            t = arr[i::gcd]\n",
    "            t.sort()\n",
    "            mid = t[len(t) // 2]\n",
    "            ans += sum([abs(x - mid) for x in t])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        length = len(arr)\n",
    "        t = gcd(k, length)\n",
    "        ans = 0\n",
    "        for i in range(t):\n",
    "            tmp = arr[i::t]\n",
    "            tmp.sort()\n",
    "            mid = tmp[len(tmp) // 2]\n",
    "            ans += sum([abs(mid - j) for j in tmp])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        print(k)\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "           # print(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        print(k)\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "           # print(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            s=0\n",
    "            #print(b)\n",
    "            for x in b:\n",
    "                s+=abs(x-mid)\n",
    "            ans=ans+s  \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        # 执行操作: 对任意元素加一或减一，是长度为k的子数组的和都相同\n",
    "        # 返回最少执行操作次数\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/make-k-subarray-sums-equal/solutions/2203591/zhuan-huan-zhong-wei-shu-tan-xin-pei-shu-4dut/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        flag=[True] * n\n",
    "        p=0\n",
    "        for i in range(n):\n",
    "            if flag[i]:\n",
    "                flag[i]=False\n",
    "                tot=[arr[i]]\n",
    "                j=(i+k)%n\n",
    "                while flag[j]:\n",
    "                    tot.append(arr[j])\n",
    "                    flag[j]=False\n",
    "                    j=(j+k)%n\n",
    "                tot.sort()\n",
    "                sp=len(tot)\n",
    "                kk=tot[sp//2]\n",
    "                for r in tot:\n",
    "                    p+=abs(r-kk)\n",
    "\n",
    "        return p\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        g = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(g):\n",
    "            b = sorted(arr[i::g])\n",
    "            mid = len(b) // 2\n",
    "            ans += sum(abs(x - b[mid]) for x in b)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(k):\n",
    "            block = sorted(arr[i::k])\n",
    "            mid = block[len(block) // 2]\n",
    "            res += sum(abs(num - mid) for num in block)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, a: List[int], k: int) -> int:\n",
    "        n=len(a)\n",
    "        k=gcd(k,n)\n",
    "        ans=0\n",
    "        for i in range(k):\n",
    "            b=sorted(a[i::k])\n",
    "            mid=b[len(b)//2]\n",
    "            ans+=sum(abs(x-mid) for x in b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "      k = gcd(k, len(arr))\n",
    "      ans = 0\n",
    "      for i in range(k):\n",
    "        b = sorted(arr[i::k])\n",
    "        mid = b[len(b)//2]\n",
    "        ans += sum(abs(x-mid) for x in b)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        if n == k:\n",
    "            return 0\n",
    "        \n",
    "        period = math.gcd(n, k)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(period):\n",
    "            nwarr = sorted(arr[i::period])\n",
    "            mid = nwarr[len(nwarr)//2]\n",
    "            ans += sum(abs(x-mid) for x in nwarr)\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k=gcd(k,len(arr))\n",
    "        res=0\n",
    "        for i in range(k):\n",
    "            b=sorted(arr[i::k])\n",
    "            mid=b[len(b)//2]\n",
    "            res+=sum(abs(x-mid) for x in b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr)) #定理\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])  # k 是步长\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans\n",
    "'''\n",
    "作者：endlesscheng\n",
    "链接：https://leetcode.cn/problems/make-k-subarray-sums-equal/solution/zhuan-huan-zhong-wei-shu-tan-xin-pei-shu-4dut/\n",
    "来源：力扣（LeetCode）\n",
    "著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import gcd\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))  # 计算 k 和数组长度的最大公约数\n",
    "        ans = 0  # 初始化答案为 0\n",
    "        for i in range(k):  # 遍历每一个可能的起点 i\n",
    "            b = sorted(arr[i::k])  # 提取从 i 开始，步长为 k 的所有元素，并排序\n",
    "            mid = b[len(b) // 2]  # 找到这些数的中位数\n",
    "            ans += sum(abs(x - mid) for x in b)  # 计算所有数变到 mid 所需的操作次数，并累加到答案\n",
    "        return ans  # 返回答案\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        b = math.gcd(n, k)\n",
    "        ans = 0\n",
    "        for i in range(b):\n",
    "            a = [arr[j] for j in range(i, n, b)] \n",
    "            a.sort()\n",
    "            mid = a[len(a)//2]\n",
    "            ans += sum([abs(x - mid) for x in a])\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b) // 2]\n",
    "            ans += sum(abs(x - mid) for x in b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def sum_arr(self, arr, k):\n",
    "        sub_sum = [0] * len(arr)\n",
    "        sub_sum[0] = sum(arr[0:k])\n",
    "        min_sub = sub_sum[0]\n",
    "        max_sub = sub_sum[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            sub_sum[i] = sub_sum[i-1] - arr[i-1] + arr[(i-1+k)%len(arr)]\n",
    "            min_sub = min(min_sub, sub_sum[i])\n",
    "            max_sub = max(max_sub, sub_sum[i])\n",
    "        return max_sub-min_sub\n",
    "\n",
    "    def find_sl(self, e_group, sl):\n",
    "        #堆排序\n",
    "        pass\n",
    "\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        # a[i] = a[i+k] = a[i+2k]... = a[(i+xk)%len(arr)]\n",
    "        # i=0,1,...k-1\n",
    "        # 一共?组，?<=len(arr) 每一组内部相同即可\n",
    "        # 每组中位数，是变动最少的\n",
    "        # 不一定一共多少组 \n",
    "        all_group = []\n",
    "        have_count = [0]*len(arr)\n",
    "\n",
    "        while 0 in have_count:\n",
    "            start = -1\n",
    "            for ei in range(len(arr)):\n",
    "                if have_count[ei] == 0:\n",
    "                    start = ei\n",
    "\n",
    "            if start!=-1:\n",
    "                current = start\n",
    "                this_count = []\n",
    "                # print(start, current)\n",
    "                while have_count[current]==0:\n",
    "                    have_count[current] = 1\n",
    "                    this_count.append(arr[current])\n",
    "                    current = (current + k)%len(arr)\n",
    "                all_group.append(this_count)\n",
    "\n",
    "        # print(all_group)\n",
    "        \n",
    "        result = 0\n",
    "        for e_group in all_group:\n",
    "            # 找中位数 rank 大小第len(e_group)//2个\n",
    "            sl = len(e_group)//2\n",
    "            # 找第sl大的数\n",
    "            if len(e_group) <= 2: #只有1个或2个值\n",
    "                val = e_group[0]\n",
    "            else:\n",
    "                # val = self.find_sl(e_group, sl)\n",
    "                val = sorted(e_group)[sl]\n",
    "            for ele in e_group:\n",
    "                result += abs(ele-val)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "1. 一个循环数组如果既有周期 n，又有周期 k，则必然有周期 m = gcd⁡(n,k)\n",
    "2. 数组分成了m组\n",
    "3. 遍历起点 [0,m-1]，间隔m取数字，进行分组。对每一组求出最少运算次数（排序后找到中位数，求所有数字和中位数之差的和）\n",
    "4. 累计所有分组的和就是答案\n",
    "'''\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        m = gcd(n, k)\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            s = sorted(arr[i::m])\n",
    "            ans += sum(abs(s[len(s)//2] - x) for x in s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        k = gcd(k, len(arr))\n",
    "        res = 0\n",
    "        for i in range(k):\n",
    "            b = sorted(arr[i::k])\n",
    "            mid = b[len(b)//2]\n",
    "            res += sum(abs(x - mid) for x in b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gcd(x, y):\n",
    "    if y == 0:\n",
    "        return x\n",
    "    else:\n",
    "        return gcd(y, x % y)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        t = gcd(len(arr), k)\n",
    "        ans = 0\n",
    "        for i in range(t):\n",
    "            tmp = sorted(arr[i::t])\n",
    "            mid= len(tmp) // 2\n",
    "            ans+= tmp[mid]*mid-sum(tmp[:mid])+sum(tmp[mid+1:])-tmp[mid]*(len(tmp)-mid-1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def sum_arr(self, arr, k):\n",
    "        sub_sum = [0] * len(arr)\n",
    "        sub_sum[0] = sum(arr[0:k])\n",
    "        min_sub = sub_sum[0]\n",
    "        max_sub = sub_sum[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            sub_sum[i] = sub_sum[i-1] - arr[i-1] + arr[(i-1+k)%len(arr)]\n",
    "            min_sub = min(min_sub, sub_sum[i])\n",
    "            max_sub = max(max_sub, sub_sum[i])\n",
    "        return max_sub-min_sub\n",
    "\n",
    "    def find_sl(self, e_group, sl):\n",
    "        #堆排序\n",
    "        pass\n",
    "\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        # a[i] = a[i+k] = a[i+2k]... = a[(i+xk)%len(arr)]\n",
    "        # i=0,1,...k-1\n",
    "        # 一共?组，?<=len(arr) 每一组内部相同即可\n",
    "        # 每组中位数，是变动最少的\n",
    "        # 不一定一共多少组 \n",
    "        all_group = []\n",
    "        have_count = [0]*len(arr)\n",
    "\n",
    "        while 0 in have_count:\n",
    "            start = -1\n",
    "            start = have_count.index(0)\n",
    "            # for ei in range(len(arr)):\n",
    "            #     if have_count[ei] == 0:\n",
    "            #         start = ei\n",
    "\n",
    "            if start!=-1:\n",
    "                current = start\n",
    "                this_count = []\n",
    "                # print(start, current)\n",
    "                while have_count[current]==0:\n",
    "                    have_count[current] = 1\n",
    "                    this_count.append(arr[current])\n",
    "                    current = (current + k)%len(arr)\n",
    "                all_group.append(this_count)\n",
    "\n",
    "        # print(all_group)\n",
    "        \n",
    "        result = 0\n",
    "        for e_group in all_group:\n",
    "            # 找中位数 rank 大小第len(e_group)//2个\n",
    "            sl = len(e_group)//2\n",
    "            # 找第sl大的数\n",
    "            if len(e_group) <= 2: #只有1个或2个值\n",
    "                val = e_group[0]\n",
    "            else:\n",
    "                # val = self.find_sl(e_group, sl)\n",
    "                val = sorted(e_group)[sl]\n",
    "            for ele in e_group:\n",
    "                result += abs(ele-val)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        k = math.gcd(n, k)\n",
    "\n",
    "        rst = 0\n",
    "        for i in range(k):\n",
    "            group = []\n",
    "            for j in range(i, n, k):\n",
    "                group.append(arr[j])\n",
    "            group.sort()\n",
    "            mid = group[len(group) // 2]\n",
    "            rst += sum(abs(x - mid) for x in group)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        vis = [False] * n\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if vis[i]:\n",
    "                continue\n",
    "            pos = i\n",
    "            a = []\n",
    "            while not vis[pos]:\n",
    "                a.append(arr[pos])\n",
    "                vis[pos] = True\n",
    "                pos = (pos + k) % n\n",
    "            a.sort()\n",
    "            t = len(a) // 2\n",
    "            for c in a:\n",
    "                ans += abs(c - a[t])\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.makeSubKSumEqual([1,4,1,3],2)\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gao(A: List[int]) -> int:\n",
    "    m = A[len(A) // 2]\n",
    "    return sum(abs(x - m) for x in A)\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, A: List[int], k: int) -> int:\n",
    "        g = gcd(len(A), k)\n",
    "        return sum(gao(sorted(A[i::g])) for i in range(g))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gao(A: List[int]) -> int:\n",
    "    m = A[len(A) // 2]\n",
    "    return sum(abs(x - m) for x in A)\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, A: List[int], k: int) -> int:\n",
    "        g = gcd(len(A), k)\n",
    "        return sum(gao(sorted(A[i::g])) for i in range(g))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def sum_arr(self, arr, k):\n",
    "        sub_sum = [0] * len(arr)\n",
    "        sub_sum[0] = sum(arr[0:k])\n",
    "        min_sub = sub_sum[0]\n",
    "        max_sub = sub_sum[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            sub_sum[i] = sub_sum[i-1] - arr[i-1] + arr[(i-1+k)%len(arr)]\n",
    "            min_sub = min(min_sub, sub_sum[i])\n",
    "            max_sub = max(max_sub, sub_sum[i])\n",
    "        return max_sub-min_sub\n",
    "\n",
    "    def find_sl(self, e_group, sl):\n",
    "        #堆排序\n",
    "        pass\n",
    "\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        # a[i] = a[i+k] = a[i+2k]... = a[(i+xk)%len(arr)]\n",
    "        # i=0,1,...k-1\n",
    "        # 一共?组，?<=len(arr) 每一组内部相同即可\n",
    "        # 每组中位数，是变动最少的\n",
    "        # 不一定一共多少组 \n",
    "        all_group = []\n",
    "        have_count = [0]*len(arr)\n",
    "\n",
    "        while 0 in have_count:\n",
    "            # start = -1\n",
    "            start = have_count.index(0)\n",
    "            # for ei in range(len(arr)):\n",
    "            #     if have_count[ei] == 0:\n",
    "            #         start = ei\n",
    "\n",
    "            if start!=-1:\n",
    "                current = start\n",
    "                this_count = []\n",
    "                # print(start, current)\n",
    "                while have_count[current]==0:\n",
    "                    have_count[current] = 1\n",
    "                    this_count.append(arr[current])\n",
    "                    current = (current + k)%len(arr)\n",
    "                all_group.append(this_count)\n",
    "\n",
    "        # print(all_group)\n",
    "        \n",
    "        result = 0\n",
    "        for e_group in all_group:\n",
    "            # 找中位数 rank 大小第len(e_group)//2个\n",
    "            sl = len(e_group)//2\n",
    "            # 找第sl大的数\n",
    "            if len(e_group) <= 2: #只有1个或2个值\n",
    "                val = e_group[0]\n",
    "            else:\n",
    "                # val = self.find_sl(e_group, sl)\n",
    "                val = sorted(e_group)[sl]\n",
    "            for ele in e_group:\n",
    "                result += abs(ele-val)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        vis = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if vis[i]: continue\n",
    "            group = []\n",
    "            j = i\n",
    "            while vis[j] == 0:\n",
    "                vis[j] = 1\n",
    "                group.append(arr[j])\n",
    "                j += k\n",
    "                j %= n\n",
    "            group.sort()\n",
    "            # print(group)\n",
    "            mid = group[len(group) // 2]\n",
    "            for x in group:\n",
    "                ans += abs(x - mid)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        def gcd(x, y):\n",
    "            if x == 0:\n",
    "                return y\n",
    "            else:\n",
    "                return gcd(y % x, x)\n",
    "        a = gcd(k, n)\n",
    "        k = a\n",
    "        dp = [SortedList() for _ in range(k)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            dp[i % k].add(arr[i])\n",
    "        res = 0\n",
    "        # if n % k == 0:\n",
    "        for li in dp:\n",
    "            ln = len(li)\n",
    "            for i in range(ln // 2):\n",
    "                res += li[ln - 1 - i] - li[i]\n",
    "        # else:\n",
    "        #     arr.sort()\n",
    "        #     for i in range(n // 2):\n",
    "        #         res += arr[n - 1 - i] - arr[i]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, a: List[int], k: int) -> int:\n",
    "        n=len(a)\n",
    "        b=[]\n",
    "        v=[False]*n\n",
    "        for i in range(n):\n",
    "            if not v[i]:\n",
    "                b.append([])\n",
    "                while not v[i]:\n",
    "                    v[i]=True\n",
    "                    b[-1].append(a[i])\n",
    "                    i=(i+k)%n\n",
    "        def func(c):\n",
    "            c.sort()\n",
    "            d=list(accumulate(c))\n",
    "            s=0\n",
    "            ans=inf\n",
    "            n=len(c)\n",
    "            for i,j in enumerate(c):\n",
    "                l=j*i-d[i-1] if i>0 else 0\n",
    "                r=d[-1]-d[i]-j*(n-i-1)\n",
    "                ans=min(ans,l+r)\n",
    "            return ans\n",
    "        ans=0\n",
    "        for i in b:\n",
    "            ans+=func(i)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        def gcd(a, b):\n",
    "            if b==0:\n",
    "                return a\n",
    "            return gcd(b,a%b)\n",
    "        k=gcd(k,n)\n",
    "        ans=0\n",
    "        for i in range(k):\n",
    "            b=sorted(arr[i::k])\n",
    "            idx=len(b)//2\n",
    "            for j in range(len(b)):\n",
    "                ans+=abs(b[j]-b[idx])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def GCD(a: int, b: int) -> int:\n",
    "    while b != 0:\n",
    "        a, b = b, a % b\n",
    "    return a\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(arr)\n",
    "        g = GCD(n, k)\n",
    "        for i in range(g):\n",
    "            a = []\n",
    "            for j in range(i, n, g):\n",
    "                a.append(arr[j])\n",
    "            a.sort()\n",
    "            i1, i2 = 0, len(a) - 1\n",
    "            while i1 < i2:\n",
    "                res += a[i2] - a[i1]\n",
    "                i1, i2 = i1 + 1, i2 - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        g=gcd(n,k)\n",
    "        d=defaultdict(list)\n",
    "        for i,x in enumerate(arr):\n",
    "            d[i%g].append(x)\n",
    "        res=0\n",
    "        for i in d.keys():\n",
    "            d[i].sort()\n",
    "            lc=0\n",
    "            lt=0\n",
    "            rc=len(d[i])\n",
    "            rt=sum(d[i])\n",
    "            ans=inf\n",
    "            for x in d[i]:\n",
    "                rc-=1\n",
    "                rt-=x\n",
    "                ans=min(ans,(x*lc-lt)+(rt-rc*x))\n",
    "                lc+=1\n",
    "                lt+=x\n",
    "            res+=ans\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        def gcd(a,b):\n",
    "            a,b=max(a,b),min(a,b)\n",
    "            if b==0:\n",
    "                return a\n",
    "            return gcd(b,a%b)\n",
    "        s=gcd(n,k)\n",
    "        L=[[] for i in range(s)]\n",
    "        for i in range(n):\n",
    "            L[i%s].append(arr[i])\n",
    "        c=0\n",
    "        for l in L:\n",
    "            l.sort()\n",
    "            x=l[len(l)//2]\n",
    "            for i in l:\n",
    "                c+=abs(x-i)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n=len(arr)\n",
    "        T=gcd(n,k)\n",
    "        ls=[[]for _ in range(T)]\n",
    "        for i,k in enumerate(arr):\n",
    "            ls[i%T].append(k)\n",
    "        ans=0\n",
    "        for l in ls:\n",
    "            l.sort()\n",
    "            mid=l[len(l)//2]\n",
    "            for now in l:\n",
    "                ans+=abs(mid-now)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        group, s, res = [], set(range(len(arr))), 0\n",
    "        for i in range(k):\n",
    "            if not s:\n",
    "                break\n",
    "            pres, l = i, []\n",
    "            while pres in s:\n",
    "                s.remove(pres)\n",
    "                l.append(arr[pres])\n",
    "                pres = (pres + k) % len(arr)\n",
    "            group.append(sorted(l))\n",
    "        for x in group:\n",
    "            mi = pres = sum(x) - x[0] * len(x)\n",
    "            for i in range(1, len(x)):\n",
    "                pres += (2 * i - len(x)) * (x[i] - x[i - 1])\n",
    "                mi = min(mi, pres)\n",
    "            res += mi\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "        k = gcd(len(arr), k)\n",
    "        f = defaultdict(list)\n",
    "        for i, x in enumerate(arr):\n",
    "            f[i % k].append(x)\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            nums = f[i]\n",
    "            n = len(nums)\n",
    "            nums.sort()\n",
    "            mid = nums[n // 2]\n",
    "            ans += sum(abs(mid - x)for x in nums)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        s, res = set(range(len(arr))), 0\n",
    "        for i in range(k):\n",
    "            if not s:\n",
    "                break\n",
    "            pres, l = i, []\n",
    "            while pres in s:\n",
    "                s.remove(pres)\n",
    "                l.append(arr[pres])\n",
    "                pres = (pres + k) % len(arr)\n",
    "            l.sort()\n",
    "            res += sum(x for x in l[(len(l) + 1) // 2:]) - sum(x for x in l[:len(l) // 2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        #a[0] a[k] a[2*k]\n",
    "        n=len(arr)\n",
    "        def gcd(a: int, b:int) -> int:\n",
    "            return a if b==0 else gcd(b,a%b)\n",
    "        k=gcd(n,k)\n",
    "        mp=defaultdict(list)\n",
    "        ans=0\n",
    "        for i,x in enumerate(arr) :\n",
    "            mp[i%k].append(x)\n",
    "        for i in range(k) :\n",
    "            f=mp[i]\n",
    "            f.sort()\n",
    "            mid=f[len(f)//2]\n",
    "            ans+=sum(abs(x-mid) for x in f)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        \n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        \n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            if i not in visited:\n",
    "\n",
    "                # 开始分组\n",
    "\n",
    "                nums = []\n",
    "\n",
    "                \n",
    "\n",
    "                # 一直循环获取对等位置\n",
    "\n",
    "                while i not in visited:\n",
    "\n",
    "                    visited.add(i)\n",
    "\n",
    "                    nums.append(arr[i])\n",
    "\n",
    "                    i += k\n",
    "\n",
    "                    i %= n\n",
    "\n",
    "                \n",
    "\n",
    "                # 最小操作次数使数组元素相等\n",
    "\n",
    "                nums.sort()\n",
    "\n",
    "                res += sum(abs(num - nums[len(nums) // 2]) for num in nums)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        '''\n",
    "            1.k为周期分组\n",
    "            2.求分组中的中位数，每个数往中位数对齐，求修改次数\n",
    "        '''\n",
    "        n = len(arr)\n",
    "        groups = defaultdict(list)\n",
    "        vst = set()\n",
    "        for i in range(n):\n",
    "            p = i\n",
    "            while True:\n",
    "                if p in vst: break\n",
    "                vst.add(p)\n",
    "                groups[i].append(arr[p])\n",
    "                p = (p+k)%n\n",
    "        \n",
    "        res = 0\n",
    "        for k,v in groups.items():\n",
    "            # 怎么求中位数？\n",
    "            v.sort()\n",
    "            if len(v)%2==0:\n",
    "                #偶数\n",
    "                mid = (v[len(v)//2] + v[len(v)//2 - 1]) // 2\n",
    "            else:\n",
    "                mid = v[len(v)//2]\n",
    "            for i in v:\n",
    "                res += abs(i-mid)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        # 等价于 隔k个 相等\n",
    "        vst = set()\n",
    "        gps = defaultdict(list)\n",
    "        n = len(arr)\n",
    "\n",
    "        for i in range(n):\n",
    "            p = i\n",
    "            if p in vst: continue\n",
    "            while True:\n",
    "                if p in vst: break\n",
    "                vst.add(p)\n",
    "                gps[i].append(arr[p])\n",
    "                p = (p + k) % n\n",
    "\n",
    "        res = 0\n",
    "        for k, v in gps.items():\n",
    "            # 往中位数对齐\n",
    "            v.sort()\n",
    "            if len(v)%2 == 0:\n",
    "                mid = (v[len(v)//2] + v[len(v)//2 - 1]) //2\n",
    "            else:\n",
    "                mid = v[len(v)//2]\n",
    "\n",
    "            for i in v:\n",
    "                res += abs(i-mid)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        if n == k:\n",
    "            return 0\n",
    "        \n",
    "        period = math.gcd(n, k)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(period):\n",
    "            nwarr = sorted(arr[i::period])\n",
    "            m = len(nwarr)\n",
    "            \n",
    "            # 判断使得nwarr相等所需的最小步骤\n",
    "            psum, ssum = [0]*(m+1), [0]*(m+1)\n",
    "            for j in range(m):\n",
    "                psum[j+1] = psum[j] + nwarr[j]\n",
    "            for j in range(m-1, -1, -1):\n",
    "                ssum[j] = ssum[j+1] + nwarr[j]\n",
    "            p = float('inf')\n",
    "            j = 0\n",
    "            while j < m:\n",
    "                jj = j + 1\n",
    "                while jj < m and nwarr[jj] == nwarr[j]:\n",
    "                    jj += 1\n",
    "                q = -psum[j] + ssum[jj] + (j-m+jj)*nwarr[j]\n",
    "                if q <= p:\n",
    "                    p = q\n",
    "                else:\n",
    "                    break\n",
    "                j = jj\n",
    "            ans += p\n",
    "        \n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        vis = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if i not in vis:\n",
    "                vis.add(i)\n",
    "                tmp = [arr[i]]\n",
    "                nxt = (i + k) % n\n",
    "                while nxt != i and nxt not in vis:\n",
    "                    tmp.append(arr[nxt])\n",
    "                    vis.add(nxt)\n",
    "                    nxt = (nxt + k) % n\n",
    "                tmp.sort()\n",
    "                if tmp:\n",
    "                    v = tmp[len(tmp) // 2]\n",
    "                    for c in tmp:\n",
    "                        ans += abs(c - v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        visited=set()\n",
    "        res=0\n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            if i not in visited:\n",
    "                nums=[]\n",
    "                while i not in visited:\n",
    "                    visited.add(i)\n",
    "                    nums.append(arr[i])\n",
    "                    i+=k\n",
    "                    i%=len(arr)\n",
    "                nums.sort()\n",
    "                res+=sum(abs(num-nums[len(nums)//2]) for num in nums)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        \n",
    "        visited = set()\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i not in visited:\n",
    "                # 开始分组\n",
    "                nums = []\n",
    "                \n",
    "                # 一直循环获取对等位置\n",
    "                while i not in visited:\n",
    "                    visited.add(i)\n",
    "                    nums.append(arr[i])\n",
    "                    i += k\n",
    "                    i %= n\n",
    "                \n",
    "                # 最小操作次数使数组元素相等\n",
    "                nums.sort()\n",
    "                res += sum(abs(num - nums[len(nums) // 2]) for num in nums)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        def func(nums):\n",
    "            n=len(nums)\n",
    "            nums.sort()\n",
    "            pre=[0 for i in range(n)]\n",
    "            sub=[0 for i in range(n)]\n",
    "            sub[n-1]=nums[-1]\n",
    "            for i in range(n):\n",
    "                pre[i]=pre[i-1]+nums[i]\n",
    "            for j in range(n-2,-1,-1):\n",
    "                sub[j]=sub[j+1]+nums[j]\n",
    "            mincha=10**14\n",
    "            for i in range(n):\n",
    "                curcha=(i+1)*nums[i]-pre[i]+sub[i]-(n-i)*nums[i]\n",
    "                if curcha<mincha:\n",
    "                    mincha=curcha\n",
    "            return mincha\n",
    "        n=len(arr)\n",
    "        k=gcd(n,k)\n",
    "        if k==1:\n",
    "            return func(arr)\n",
    "        r=0\n",
    "        for i in range(k):\n",
    "            ls=[]\n",
    "            for j in range(i,n,k):\n",
    "                ls.append(arr[j])\n",
    "            #print(ls)\n",
    "            r+=func(ls)\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        n = len(arr)\n",
    "        fa = [i for i in range(n)]\n",
    "        sz = [1] * n\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def union(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fx] = fy\n",
    "                sz[fy] += sz[fx]\n",
    "        \n",
    "        for i in range(n):\n",
    "            union(i, (i+k)%n)\n",
    "        \n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            g[find(i)].append(arr[i])\n",
    "                    \n",
    "        ans = 0\n",
    "        for x in g:\n",
    "            if len(x) != 0:\n",
    "                x.sort()\n",
    "                m = x[len(x) // 2]\n",
    "                for y in x:\n",
    "                    ans += abs(m - y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, arr: List[int], k: int) -> int:\n",
    "        def find(l):\n",
    "            l.sort()\n",
    "            t = len(l)\n",
    "            mid = 0\n",
    "            if t%2 != 0:\n",
    "                mid = l[t//2]\n",
    "            else:\n",
    "                mid = (l[t//2-1]+l[t//2])//2\n",
    "            ans = 0\n",
    "            for i in l:\n",
    "                ans += abs(i-mid)\n",
    "            return ans\n",
    "        if k == len(arr):\n",
    "            return 0\n",
    "        if k == 1:\n",
    "            return find(arr)\n",
    "        d = {}\n",
    "        n = len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            d[i] = 0\n",
    "        count = 0\n",
    "        now = 1\n",
    "        i = 0\n",
    "        while count < len(arr):\n",
    "            j = 0\n",
    "            while d[(i+j*k)%n] == 0:\n",
    "                d[(i+j*k)%n] = now\n",
    "                j += 1\n",
    "                count += 1\n",
    "            i += 1\n",
    "            now += 1\n",
    "        # print(d)\n",
    "\n",
    "        \n",
    "        l = [[] for i in range(now-1)]\n",
    "        for i in range(n):\n",
    "            l[d[i]-1].append(arr[i])\n",
    "        \n",
    "        ans = 0\n",
    "        for i in l:\n",
    "            ans += find(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeSubKSumEqual(self, a: List[int], k: int) -> int:\n",
    "        n=len(a)\n",
    "        ufs=list(range(n))\n",
    "        def find(x):\n",
    "            if x==ufs[x]:\n",
    "                return x\n",
    "            ufs[x]=find(ufs[x])\n",
    "            return ufs[x]\n",
    "        def union(x,y):\n",
    "            ux,uy=find(x),find(y)\n",
    "            if ux!=uy:\n",
    "                ufs[ux]=uy\n",
    "        for i in range(n):\n",
    "            union(i,(i+k)%n)\n",
    "        h=defaultdict(list)\n",
    "        for i in range(n):\n",
    "            h[find(i)].append(i)\n",
    "        def func(c):\n",
    "            c.sort()\n",
    "            d=list(accumulate(c))\n",
    "            s=0\n",
    "            ans=inf\n",
    "            n=len(c)\n",
    "            for i,j in enumerate(c):\n",
    "                l=j*i-d[i-1] if i>0 else 0\n",
    "                r=d[-1]-d[i]-j*(n-i-1)\n",
    "                ans=min(ans,l+r)\n",
    "            return ans\n",
    "        ans=0\n",
    "        for i in h.values():\n",
    "            ans+=func([a[j] for j in i])\n",
    "        return ans\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
